package sort;

//希尔排序
public class ShellSort {
	public static void shell(int[] arr,int gap) {
		for(int i=gap;i<arr.length;i++) {
			
			for(int j=i;j>=gap;j-=gap) {
				if(arr[j-gap]>arr[j]) {
					Swap.swap(arr, j-gap, j);
				}
				else {
					break;
				}
			}
		}
	}
	
	public static void shellSort(int[] arr) {
		int gap=arr.length;
		while(gap>1) {
			gap/=2;
			shell(arr, gap);
		}
	}
	
	public static void main(String[] args) {
		int[] arr=new int[]{9,8,7,6,5,4,3,2,1};
		shellSort(arr);
		for(int x:arr) 
			System.out.print(x+" ");
	}
}
